There have hitherto been known technologies for generating information on a new road that is not present in map information on the basis of a travel history of a vehicle. For example, Japanese Patent No. 4559551 discloses a configuration in which the position of a vehicle and a geographical database are matched with each other to decide the splitting position of a link for which matching was previously established from the initial position at which matching is not established to create a new link that has the splitting point as an end point. Meanwhile, Japanese Patent Application Publication No. 2009-192480 (JP 2009-192480 A) discloses a configuration in which a track obtained in a state in which the position on a road cannot be estimated is translated, rotated, and enlarged such that the start point and the end point of the state in which the position on a road cannot be estimated match a location obtained immediately before the state in which the position on a road cannot be estimated is established and a location obtained immediately after a state in which the position on a road can be estimated is established, respectively.